CF1270X Good Bye 2019

2019年的最后一场CF，参加的人很多，按理说上分更容易，但我没有把握住机会，差点变成goodbye rating 2019

作为难得的9题场，题目质量很高，囊括了几何题，构造题，交互题，数学题等等，于是我来统一写篇题解，包括题A、B、C、D、E、G。（F先咕着，我看懂再说）

CF1270A Card Game

题意：

两个人打牌，牌可以重复出，保证牌的点数不同，点数大的人获胜

题解：

水出天际的一道题，看看第一个人那有没有牌n就行了

代码：

void doit(){
    int n,a,b;
    bool flag=0;
    read(n);read(a);read(b);
    for(int i=1,x;i<=a;i++){
        read(x);
        if(x==n) flag=1;
    }
    for(int i=1,x;i<=b;i++)
        read(x);
    if(flag) puts("YES");
    else puts("NO");
}

CF1270B Interesting Subarray

题意：

给出一个序列，请构造出一个所给序列的子序列，使得该子序列中的最大值-最小值>=子序列长度

题解：

由于没有长度限制，因此只要$O(n)$扫一遍判断每个长度为2的子序列（也就是相邻的两个数）是否合法即可

代码：

void doit(){
    int n,flag=0;
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        if(i==1) continue;
        if(abs(a[i]-a[i-1])>1) flag=i-1;
    }
    if(flag){
        puts("YES");
        write(flag);putchar(' ');write(flag+1);puts("");
    }
    else{
        puts("NO");
    }
}

CF1270C Make Good

题意：

给出一个长度为$n$的序列$a_1…a_n$，请随意添加$k$个数$a_{n+1}…a_{n+k}$，满足$k\in[0,3]$，使得$\sum\limits_{i=1}^{n+k}a_i=2\cdot\oplus_{i=1}^{n+k}a_i$

题解：

因为没有要求最小化$k$，我们可以考虑这样构造：先添加一个数$a_{n+1}$使得$\oplus_{i=1}^{n+1}a_i=0$，由于异或的性质，这是十分容易实现的：$a_{n+1}=\oplus_{i=1}^{n}a_i$

此时可以把这$n+1$个数看做常数，我们还要添加的数$a_{n+2}$为未知数，就得到了一个一元一次方程$\sum\limits_{i=1}^{n+1}+a_{n+2}=2*a_{n+2}$，依式化简算出就可以得到$a_{n+2}$

这样，无论给出怎样的序列$a$，都只需要添加至多两个数$a_{n+1}$和$a_{n+2}$就可以满足条件

代码：

void doit(){
    int n,sum=0,p=0;
    read(n);
    for(int i=1,x;i<=n;i++) p^=read(x),sum+=x;
    puts("2");
    write(p),putchar(' ');write(p+sum);
    puts("");
}

CF1270D Strange Device

看这里

CF1270E Divide Points

看这里

CF1270G Subset with Zero Sum

看这里